from typing import List


class Solution:
    def splitArray(self, nums: List[int], k: int) -> int:
        l = 0
        r = int(1e10)

        def f(limit):
            cnt = 1  # 至少有一个子数组
            current_sum = 0
            for num in nums:
                if num > limit:
                    return False
                if current_sum + num > limit:
                    cnt += 1
                    current_sum = num
                else:
                    current_sum += num
            return cnt <= k

        while l <= r:
            m = (l + r) >> 1
            if f(m):
                r = m - 1
            else:
                l = m + 1
        return r + 1


if __name__ == '__main__':
    s = Solution()
    r = s.splitArray(nums=[1, 60, 25, 25, 1, 1, 30, 110, 40, 70, 37], k=4)
    print(r)
